perm filename A82.TEX[106,PHY] blob
sn#826049 filedate 1986-10-07 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00003 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 \magnification\magstephalf
C00018 00003 \noindent
C00024 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
January\or February\or March\or April\or May\or June\or
July\or August\or September\or October\or November\or December\fi
\space\number\day, \number\year}
\baselineskip 14pt
\rm
\parskip 6pt
\line{\sevenrm a82.tex[106,phy] \today\hfill}
\bigskip
As yet, the only actions we have repeated have been simple printing commands.
Some tasks,
though, require repeating subalgorithms that themselves use repetition.
To print this sequence:
\smallskip
{\obeylines\obeyspaces\let =\ \tt
2 3 4 5 13 14 15 16 24 25 26 27 35 36 37 38 46 47 48 49
}
\smallskip\noindent
by a program of the form
\smallskip
{\obeylines\obeyspaces\let =\ \tt
FOR I:= 1 TO 20 DO
WRITELN( f(I) )
}
\smallskip\noindent
is an unpromising task (although there is a way to do it). The sequence breaks
into natural groups of four numbers each, each of which is simply expressed
by iteration. Let's look at the sequence again, labeling each number with two
indices: the group number,~{\tt I}, and the position~{\tt J} within the group,
counting from zero.
$$\vcenter{\halign{\hfil{#}\hfil\quad&\hfil{#}\quad&\hfil{#}\quad%
&\hfil{#}\quad%
&\hfil{#}\quad&\hfil{#}\quad&\hfil{#}\quad&\hfil{#}\quad%
&\hfil{#}\quad&\hfil{#}\quad%9
&\hfil{#}\quad&\hfil{#}\quad&\hfil{#}\quad&\hfil{#}\quad%
&\hfil{#}\quad&\hfil{#}\quad%15
&\hfil{#}\quad&\hfil{#}\quad&\hfil{#}\quad&\hfil{#}\quad%
&\hfil{#}\cr
I&0&0&0&0&1&1&1&1&2&2&2&2&3&3&3&3&4&4&4&4\cr
J&0&1&2&3&0&1&2&3&0&1&2&3&0&1&2&3&0&1&2&3\cr
f(I,J)&2&3&4&5&13&14&15&16&24&25&26&27&35&36&37&38&46&47&48&48\cr}}$$
Each number within a group is larger by one than the one before it. Each
group is larger by eleven than the one before it. The general formula is
{\tt f(I,J)=2+J+11*I}.
For each~{\tt I} in turn, the {\tt I}th group can be printed by
\smallskip
{\obeylines\obeyspaces\let =\ \tt
FOR J := 0 TO 3 DO
WRITELN(2 + J + 11*I)
}
\smallskip\noindent
Rather than write the above subalgorithm out five times with {\tt 0}, {\tt 1},
{\tt 2}, {\tt 3}, and {\tt 4} substituted for~{\tt I}, we can use iteration
on it, in the pattern:
\smallskip
{\obeylines\obeyspaces\let =\ \tt
FOR I := 0 TO 4 DO
{\rm (the above subalgorithm)}
}
\smallskip\noindent
giving the complete program body:
\smallskip
{\obeylines\obeyspaces\let =\ \tt
FOR I := 0 TO 4 DO
FOR J := 0 TO 3 DO
WRITELN(2 + J + 11*I)
}
Generally, given a complicated pattern of actions to perform, look for
ways to break it into subsequences that are simpler. Number the subsequences
in a regular way, and determine how the subsequence depends on its index.
Then find a program for a typical subsequence.
\vfill\eject
To print this multiplication table
\smallskip
{\obeylines\obeyspaces\let =\ \tt
1*1 = 1
2*1 = 2
2*2 = 4
3*1 = 3
3*2 = 6
3*3 = 9
4*1 = 4
4*2 = 8
4*3 = 12
4*4 = 16
}
\smallskip\noindent
I notice that the `{\tt 2*...}' lines are printed by
\smallskip
{\obeylines\obeyspaces\let =\ \tt
FOR I:=1 TO 2 DO
WRITELN(2,'*',I,'=',2*I)
}
\smallskip\noindent
and the `{\tt 3*...}' lines are printed by
\smallskip
{\obeylines\obeyspaces\let =\ \tt
FOR I:=1 TO 3 DO
WRITELN(3,'*',I,'=',3*I)
}
\smallskip\noindent
where I skipped the `{\tt 1*}' lines because, as often happens at the
beginning or end of a pattern, it is too simple compared to the others.
Comparing the two program fragments, I~see that
\smallskip
{\obeylines\obeyspaces\let =\ \tt
FOR I:=1 TO J DO
WRITELN(J,'*',I,'=',J*I)
}
\smallskip\noindent
represents both, and can be iterated with {\tt J=1,2,3,4}.
The whole table can be printed by
\smallskip
{\obeylines\obeyspaces\let =\ \tt
FOR J:=1 TO 4 DO
FOR I:=1 TO J DO
WRITELN(J,'*',I,'=',J*I)
}
\smallskip
An iteration in which the repeated statement is itself an iteration
is called a {\it nested\/} iteration. If, as in the example above, the
number of executions of the inner iteration varies, at least the limit
expressions of the inner iteration will depend on the outer iteration
variable. The two variables must have distinct names.
In the examples above, we have gone from a description of the sequence of
actions needed to a simple or nested iteration that performs those actions.
Sometimes, though, I~have a program, but don't know what it does. I~might have
received it in the mail, or having written it myself, I~might want to check
it ``by hand''.
There are many good reasons for executing a program ``by hand'', including:
\smallskip\disleft25pt:
(1): A program may be desk-checked on a small problem to which the
answer is known. Unexpected intermediate results show likely
locations for errors.
\smallskip\disleft25pt:
(2): A program written by another person can be hand executed to get
insight into the logic of its design.
\smallskip\noindent
To hand-execute an iteration of the form {\tt FOR I:= A TO B DO S}:
\smallskip\disleft25pt:
(1): Evaluate {\tt A} and {\tt B} getting numerical values
$N↓{\hbox{\tt A}}$ and $N↓{\hbox{\tt B}}$
\smallskip\disleft25pt:
(2): Write down {\tt FOR I:=$N↓{\hbox{\tt A}}$ TO $N↓{\hbox{\tt B}}$ DO}
\smallskip\disleft25pt:
(3): Draw a vertical rectangle, leaving it open at the bottom until
you know how much room the execution will take.
\smallskip\disleft25pt:
(4): Inside the rectangle, write {\tt I=$N↓{\hbox{\tt A}}$}
\smallskip\disleft25pt:
(5): If {\tt I $≤ N↓{\hbox{\tt B}}$},
hand-execute command~{\tt S}; otherwise go to step~7.
If {\tt S} is itself an iteration its execution record will be a
second rectangle inside the first one.
\smallskip\disleft25pt:
(6): Draw a faint or dotted line across the rectangle. Then
write down {\tt I =} (one greater than the previous value) and return to
step~5.
\smallskip\disleft25pt:
(7): Close off the bottom of the rectangle, and write
{\tt 'I=?'}, to show that after completion of an iteration,
the iteration variable is left with an unspecified value.
\vfill\eject
%\bigskip
\noindent
{\bf Example:}\quad {\tt FOR I:=1 TO 4 DO WRITE(I * I)}
\bigskip
{\baselineskip 10pt
{\obeylines\obeyspaces\let =\ \tt
FOR I:=1 TO 4 DO
I=1
WRITE(I*I) 1
I=2
WRITE(I*I) 4
I=3
WRITE(I*I) 9
I=4
WRITE(I*I) 16
I=5
I=?
}
}
\vfill\eject
{\baselineskip 10pt
\noindent
{\bf Example:} {\tt FOR I:=1 TO 3 DO}
\smallskip
{\obeylines\obeyspaces\let =\ \tt
FOR J:=I+1 TO 3 DO
WRITE(I * J)
FOR I:=1 TO 3 DO
I=1
FOR J:=2 TO 3 DO
J=2
WRITE(I*J) 2
J=3
WRITE(I*J) 3
J=4
J=?
I=2
FOR J:=3 TO 3 DO
J=3
WRITE(I*J) 6
J=4
J=?
I=3
FOR J:=4 TO 3 DO
J=4
{\rm(no other action)}
J=?
I=4
I=?
}
}
\medskip
Because of the similarity of the rectangles to contour lines on a map, this
method is called the {\sl contour model\/} of program execution.
As we go deeper
into Pascal, we will find other features of the language that introduce
contour lines, each with its own rules for filling in the boxes.
\vfill\eject
%\medskip
{\baselineskip 10pt
{\obeylines\obeyspaces\let =\ \tt
PROGRAM WALLPAPER (OUTPUT):
VAR vertical,
row,
horizontal,
column : integer;
BEGIN
FOR vertical:=1 TO 2 DO
FOR row:=-4 TO 4 DO
BEGIN
FOR horizontal:=1 TO 4 DO
BEGIN
FOR column:=1 TO ABS(row) DO WRITE (' ');
FOR column:=1 TO 9-2*ABS(row) DO WRITE ('*');
FOR column:=1 TO ABS(row) DO WRITE (' ');
END
WRITELN
END
END.
}
}
\bigskip
{\baselineskip0pt
{\obeylines\obeyspaces\let =\ \tt
* * * *
*** *** *** ***
***** ***** ***** *****
******* ******* ******* *******
************************************
******* ******* ******* *******
***** ***** ***** *****
*** *** *** ***
* * * *
* * * *
*** *** *** ***
***** ***** ***** *****
******* ******* ******* *******
************************************
******* ******* ******* *******
***** ***** ***** *****
*** *** *** ***
* * * *
}
}
\bigskip
\line{\copyright 1984 Robert W. Floyd; First draft March 28, 1984\hfil}
%\line{First draft (not published) April 1, l985.\hfill}
%First draft (not published) October 7, 1985\hfil}
%revised: Date; subsequently revised.\hfill}
\bye
\noindent
{\bf Example:}\quad {\tt FOR I:=1 TO 4 DO WRITE(I * I)}
\bigskip
{\obeylines\obeyspaces\let =\ \tt
FOR I:=1 TO 4 DO
\smallskip
I=1
WRITE(I*I) 1
\smallskip
I=2
WRITE(I*I) 4
\smallskip
I=3
WRITE(I*I) 9
\smallskip
I=4
WRITE(I*I) 16
\smallskip
I=5
\smallskip
I=?
}
\vfill\eject
\noindent
{\bf Example:} {\tt FOR I:=1 TO 3 DO}
\smallskip
{\obeylines\obeyspaces\let =\ \tt
FOR J:=I+1 TO 3 DO
WRITE(I * J)
}
\bigskip
{\obeylines\obeyspaces\let =\ \tt
FOR I:=1 TO 3 DO
\smallskip
I=1
FOR J:=2 TO 3 DO
\smallskip
J=2
WRITE(I*J) 2
\smallskip
J=3
WRITE(I*J) 3
\smallskip
J=4
\smallskip
J=?
\smallskip
I=2
FOR J:=3 TO 3 DO
\smallskip
J=3
WRITE(I*J) 6
\smallskip
J=4
\smallskip
J=?
\smallskip
I=3
FOR J:=4 TO 3 DO
\smallskip
J=4
{\rm(no other action)}
%\smallskip
J=?
\smallskip
I=4
\smallskip
I=?
}
\medskip
Because of the similarity of the rectangles to contour lines on a map, this
method is called the {\sl contour model\/} of program execution.
As we go deeper
into Pascal, we will find other features of the language that introduce
contour lines, each with its own rules for filling in the boxes.
\medskip
{\obeylines\obeyspaces\let =\ \tt
PROGRAM WALLPAPER (OUTPUT):
VAR vertical,
row,
horizontal,
column : integer;
BEGIN
FOR vertical:=1 TO 2 DO
FOR row:=-4 TO 4 DO
BEGIN
FOR horizontal:=1 TO 4 DO
BEGIN
FOR column:=1 TO ABS(row) DO WRITE (' ');
FOR column:=1 TO 9-2*ABS(row) DO WRITE ('*');
FOR column:=1 TO ABS(row) DO WRITE (' ');
END
WRITELN
END
END.
}
\bigskip
{\baselineskip0pt
{\obeylines\obeyspaces\let =\ \tt
* * * *
*** *** *** ***
***** ***** ***** *****
******* ******* ******* *******
************************************
******* ******* ******* *******
***** ***** ***** *****
*** *** *** ***
* * * *
* * * *
*** *** *** ***
***** ***** ***** *****
******* ******* ******* *******
************************************
******* ******* ******* *******
***** ***** ***** *****
*** *** *** ***
* * * *
}
}
\bigskip
\line{\copyright 1984 Robert W. Floyd; First draft March 28, 1984\hfil}
%\line{First draft (not published) April 1, l985.\hfill}
%First draft (not published) October 7, 1985\hfil}
%revised: Date; subsequently revised.\hfill}
\bye